package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description TODO
 *
 * @ClassName algorithm.sort.PartitionAndQuickSort
 * @Version 1.0
 * @Date: 2022/2/18 9:58
 * @Author xuyi
 */
public class PartitionAndQuickSort {

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test2(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test3(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort3(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }

    public void sort2(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        quickSort2(arr,0,arr.length-1);
    }

    public void sort3(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        quickSort3(arr,0,arr.length-1);
    }

    /**
     * 一次排一个数
     */
    private void quickSort(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int partition = partition(arr, L, R);
        quickSort(arr,L,partition-1);
        quickSort(arr,partition+1,R);
    }

    /**
     * 一次排多个数
     */
    private void quickSort2(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int[] ints = netherlandsFlag(arr, L, R);
        quickSort2(arr,L,ints[0]-1);
        quickSort2(arr,ints[1]+1,R);
    }

    /**
     * 一次排多个数
     * 并且随机选择基准数，进一步降低排序的时间复杂度
     */
    private void quickSort3(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        //随机选择位置，与arr[R]上的数做交换
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
//        swap(arr,L+(int)(Math.random()*(R-L+1)),R);
        int[] ints = netherlandsFlag(arr, L, R);
        quickSort3(arr,L,ints[0]-1);
        quickSort3(arr,ints[1]+1,R);
    }

    /**
     * 将数组arr下标在[L,R]中比arr[R]小的排到数组的左边，比arr[R]大的排在数组右边，arr[R]排在两者中间
     * 返回arr[R]的下标
     */
    private int partition(int[] arr,int L,int R){
        if(L>R){
            return -1;
        }
        if(L==R){
            return L;
        }
        //设置le为小于等于区域的右下标
        int le = L-1;
        int idx = L;
        //对【idx，R-1】范围中的元素进行分组
        while(idx<R){
            if(arr[idx]<=arr[R]){
                swap(arr,idx,++le);
            }
            idx++;
        }
        //将下标为R的元素交换到最终位置
        swap(arr,++le,R);
        return le;
    }

    /**
     * 将数组arr下标在[L,R]中比arr[R]小的排到数组的左边，比arr[R]大的排在数组右边，等于arr[R]排在两者中间
     * 返回等于arr[R]区域的左右下标
     */
    public int[] netherlandsFlag(int[] arr, int L, int R){
        if(L>R){
            return new int[]{-1,-1};
        }
        if(L==R){
            return new int[]{L,L};
        }
        //设置l、r分别为小于区域的右下标和大于区域的左下标
        int l = L-1,r = R;
        int idx = L;
        //小于区域的右下标大于等于大于区域的左下标时跳出循环，此时只有下标为R的数没有终于最终位置
        while(idx<r){
            if(arr[idx]==arr[R]){
                idx++;
            }else if(arr[idx]<arr[R]){
                swap(arr,++l,idx++);
            }else{
                swap(arr,--r,idx);
            }
        }
        //将下标为R的数交换到最终位置
        swap(arr,r,R);
        return new int[]{l+1,r};
    }

    private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
